package com.zy.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhaoyi
 * @date 2021/12/20 6:35 下午
 * 广度优先搜索
 */
public class BFS {


    public static boolean search(Graph graph, Integer src, Integer dest) {
        LinkedList<Integer>[] table = graph.getTable();
        if (graph.getCount() <= src) {
            return false;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(src);
        boolean[] visited = new boolean[graph.getCount()];
        visited[0] = true;

        //注意这个存放路径这块...
        //prev[i]存储的是，顶点 i 是从哪个前驱顶点遍历过来的。
        //比如，我们通过顶点2的邻接表访问到顶点 3，那prev[3]就等于2
        int[] prev = new int[graph.getCount()];
        for (int i = 0; i < graph.getCount(); i++) {
            prev[i] = -1;
        }

        while (!queue.isEmpty()) {
            Integer ds = queue.poll();
            if (ds.equals(dest)) {
                //找到打印路径
                print(prev, src, dest);
                return true;
            } else {
                LinkedList<Integer> ls = table[ds];
                for (Integer i : ls) {
                    if (!visited[i]) {
                        prev[i] = ds;
                        queue.add(i);
                        visited[i] = true;
                    }
                }
            }
        }
        return false;
    }

    //递归打印s->t的路径
    public static void print(int[] prev, int s, int t) {
        if (prev[t] != -1 && t != s) {
            print(prev, s, prev[t]);
        }
        System.out.print(t + " -- ");
    }




}
